#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/*
	用堆排序实现降序排列。
*/

void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

int *heap(int array[], int n, int type)
{
	int i, j;
	for (i = 0; i < pow(2, ceil(log2(n)) - 1) - 1; i++)
	{
		if (type < 0)
		{
			for (j = n - 1; j > i; j--)
			{
				if (array[(j - 1) / 2] > array[j])
				{
					swap(&array[(j - 1) / 2], &array[j]);
				}
			}
		}
		else
		{
			for (j = n - 1; j > i; j--)
			{
				if (array[(j - 1) / 2] < array[j])
				{
					swap(&array[(j - 1) / 2], &array[j]);
				}
			}
		}
	}
	return array;
}

void HeapSort(int array[], int n, int mode)
{
	int i;
	for (i = 0; i < n; i++)
	{
		heap(array + i, n - i, mode);
	}
}

int main()
{
	int array[1000];
	int i;
	for (i = 0; i < 1000; i++)
	{
		array[i] = rand() % 10000;
	}
	HeapSort(array, 1000, 1);
	int tag = 0;
	for (i = 0; i < 999; i++)
	{
		if (array[i] < array[i + 1])
		{
			tag = -1;
		}
	}
	printf("tag=%d\n", tag);
	return 0;
}
